﻿P1060[NOIP 2006 普及组] 开心的金明


题目描述
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 N 元。于是，他把每件物品规定了一个重要度，分为 5 等：用整数 1−5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为 v
j
​
，重要度为 w
j
​
，共选中了 k 件物品，编号依次为 j
1
​
, j
2
​
, …, j
k
​
，则所求的总和为：

v
j
1
​

​
×w
j
1
​

​
+ v
j
2
​

​
×w
j
2
​

​
… + v
j
k
​

​
×w
j
k
​

​

请你帮助金明设计一个满足要求的购物单。

输入格式
第一行，为 2 个正整数，用一个空格隔开：n, m（n < 30000, m < 25）其中 n 表示总钱数，m 为希望购买物品的个数。

	从第 2 行到第 m + 1 行，第 j 行给出了编号为 j−1 的物品的基本数据，每行有 2 个非负整数 v, p（其中 v 表示该物品的价格(v≤10000)，p 表示该物品的重要度（1≤p≤5）。

	输出格式
	1 个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（ < 100000000）。

	输入输出样例
	输入 #1复制

	1000 5
	800 2
	400 5
	300 5
	400 3
	200 2
	输出 #1复制

	3900
	说明 / 提示
	NOIP 2006 普及组 第二题



	//思路：每个组有n个人，能力相同的人在一组就会这个重复的能力变成0；因此想到异或；以及后面的价值关于2的多少次方，因此考虑到了
//位运算得到的，因此可以把每个人的能力位操作到一个ull类型的值上（k大于32）；保存起来，然后找这些人中的子集使得全部异或起来
//终值最大即可-->纯dfs问题 

#include<bits/stdc++.h> 
#define  IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
int n, m;
int V[31], P[31];//对应的钱数与重要度 
int final_ans = 0;
bool choice[31];
//dfs(pos) ：能完成从第pos个人的位置通过选与不选到最后一个人完成最终的ans的更新！ 
void dfs1(int pos) {
	//递归出口
	if (pos == m) {
		int real_v = 0;
		for (int i = 0; i < m; i++)  if (choice[i])	real_v += V[i];

		if (real_v > n) return;//总钱上限 
		int middle_ans = 0;
		for (int i = 0; i < m; i++)if (choice[i]) middle_ans += V[i] * P[i];//计算中间值和 
		final_ans = max(middle_ans, final_ans);//跟新最大值 
		return;
	}
	//主体

	//选pos处的物品 
	choice[pos] = 1;
	dfs1(pos + 1);
	//不选pos处的物品 
	choice[pos] = 0;
	dfs1(pos + 1);

	//void 不用返回 
}

//这里直接每次的dfs都把对应的此时的ans都统计好了，最后就不需要在遍历计算了 ；这个更好理解dfs-->选与不选都能通过价值->对应的参数；
//在dfs函数头中体现出来 !(函数头即当前到达的位置，选了还是没选对应的此时的总价值，有点接近dp表示的意思)
void dfs2(int pos, int cur_ans) {//记录遍历的当前的位置以及通过选与不选到当前位置得到的总值 
	//递归出口
	if (pos == m) {
		int real_v = 0;
		for (int i = 0; i < m; i++)  if (choice[i])	real_v += V[i];

		if (real_v > n) return;//总钱上限 

		final_ans = max(cur_ans, final_ans);//跟新最大值 
		return;
	}
	//主体

	//选pos处的物品 
	choice[pos] = 1;
	dfs2(pos + 1, cur_ans + V[pos] * P[pos]);
	//不选pos处的物品 
	choice[pos] = 0;
	dfs2(pos + 1, cur_ans);

	//void 不用返回 

}
//子集问题
void dfs_solve() {

	cin >> n >> m;
	for (int i = 0; i < m; i++) cin >> V[i] >> P[i];
	//dfs1(0);
	dfs2(0, 0);
	cout << final_ans << endl;

}

//01背包 
int dp_2[31][10006] = { 0 };

void _2dp_solve() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) cin >> V[i] >> P[i];

	for (int i = 1; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			dp_2[i][j] = max(dp_2[i - 1][j], j >= V[i] ? dp_2[i - 1][j - V[i]] + V[i] * P[i] : 0);
		}
	}
	cout << dp_2[m][n] << endl;

}

int dp_1[10006];

//01背包降维 
void _1dp_solve() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) cin >> V[i] >> P[i];

	for (int i = 1; i <= m; i++) {
		for (int j = n; j >= V[i]; j--) {
			dp_1[j] = max(dp_1[j], dp_1[j - V[i]] + V[i] * P[i]);
		}
	}
	cout << dp_1[n] << endl;

}
int main() {
	IOS;
	_1dp_solve();
	//	_2dp_solve();
	 //dfs_solve();
	return 0;
}